package com.zx._12_算法.algorithm.letcode;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: 数字生成短链
 * @Description: 面试题68 - II. 二叉树的最近公共祖先   (完全二叉树才能使用数组呢)
 *         给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *         百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *         例如，给定如下二叉树: root =[3,5,1,6,2,0,8,7,4]
 * @author: zhangxue
 * @date: 2020年3月25日下午5:45:24
 * @company: 未知
 * @Copyright: Copyright (c) 2015
 */
public class Demo1 {

    public static void main(String[] args) {
//		示例1:
//		输入: root = [3,5,1,6,2,0,8,7,4], p = 5, q = 1
//		输出: 3
//		解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
        Integer[] tree = {3, 5, 1, 6, 2, 0, 8, 7, 4};
        int found = found(tree, 0, 5, 1);
        System.out.println(tree[found]);

//		示例2:
//		输入: root = [3,5,1,6,2,0,8,7,4], p = 5, q = 4
//		输出: 5
//		解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
        Integer[] tree2 = {3, 5, 1, 6, 2, 0, 8, 7, 4};
        int found2 = found(tree2, 0, 5, 4);
        System.out.println(tree2[found2]);
    }

    /**
     * @param tree
     * @param now
     * @param p
     * @param q
     * @return
     * @Title: 递归发现当前节点是否是需要的数据
     * @Description: -1=发现一个          -2=没有发现    >=0的数字，就是已经找到了
     * @date: 2020年3月26日上午10:02:15
     * @author: zhangxue
     */
    public static int found(Integer[] tree, int now, int p, int q) {
        int nowData = tree[now];
        int foundLen = -2;// 发现了几个，默认-2 没有发现
        if (nowData == p || nowData == q) {
            foundLen++;// 发现一个
        }
        int leftIndex = 2 * now + 1;
        int rightIndex = 2 * now + 2;
        // 继续往下找
        if (leftIndex < tree.length) {
            int t = found(tree, leftIndex, p, q);
            if (t == -1) {
                foundLen++;// 发现一个
            } else if (t == -2) {
                // 啥都不做
            } else {// 发现两个了
                return t;
            }
        }

        // 继续往下找
        if (rightIndex < tree.length) {
            int t = found(tree, rightIndex, p, q);
            if (t == -1) {
                foundLen++;// 发现一个
            } else if (t == -2) {
                // 啥都不做
            } else {// 发现两个了
                return t;
            }
        }

        if (foundLen == -1) {
            // 发现一个
        } else if (foundLen == -2) {
            // 啥都不做
        } else {// 发现两个了
            return now;
        }
        return foundLen;
    }


}
